package com.zdp.algorithm.linkedlist;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 反转链表
 * @author Zhengdp
 * @date 2023年02月14日 14:44
 */
public class ReverseLinkedList {
    public static void main(String[] args) throws IOException {
        ReverseLinkedListImpl1 impl1 = new ReverseLinkedListImpl1();
        ReverseLinkedListImpl2 impl2 = new ReverseLinkedListImpl2();
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(input.readLine());
        String[] s1 = input.readLine().split(" ");
        Node head1 = Node.createNodeList(s1);
        int m = Integer.valueOf(input.readLine());
        String[] s2 = input.readLine().split(" ");
        TwoNode head2 = TwoNode.createNodeList(s2);
        Node h1 = impl1.reverseNode(head1);
        TwoNode h2 = impl2.reverseNode(head2);
        while(h1 != null){
            System.out.print(h1.value + " ");
            h1 = h1.next;
        }
        System.out.println();
        while(h2 != null){
            System.out.print(h2.data + " ");
            h2 = h2.next;
        }
    }
}

/**
 * 反转单向链表
 */
class ReverseLinkedListImpl1 {
    public Node reverseNode(Node head){
        if(head.next == null || head.next.next == null){
            return head.next;
        }
        Node pre = null;
        Node next = null;
        Node cur  = head.next;
        while(cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

/**
 * 反转双向链表
 */
class ReverseLinkedListImpl2 {
    public TwoNode reverseNode(TwoNode head){
        if(head.next == null || head.next.next == null){
            return head.next;
        }
        TwoNode pre = null;
        TwoNode next = null;
        TwoNode cur = head.next;
        while(cur != null){
            next = cur.next;
            cur.pre = next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;

    }
}
